package _04;

import java.util.Scanner;

/**
 * @author ：Rwto
 * @date ：Created in 2021/7/12 10:42
 * @description：二维数组的查找 最坏时间复杂度O(n*m)  暴力求解改进后。
 */
public class Solution01 {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        if(matrix==null||matrix.length==0)
            return false;
        int n = matrix.length;
        int m = matrix[0].length;
        for(int i = 0; i<n; i++){
            for(int j = 0; j< m; j++){
                if(matrix[i][j]==target)
                    return true;
                else if(matrix[i][j]>target){
                    m = j; break;
                }

            }
        }

        return false;
    }

    public static void  main(String[] args){
        Scanner sc = new Scanner(System.in);
        System.out.println("输入行和列");
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[][] matrix = new int[n][m];
        System.out.println("输入二维数组");

        for(int i = 0 ;i<n ;i++){
            for(int  j = 0; j<m ; j++){
                int tmp = sc.nextInt();
                matrix[i][j] = tmp;
            }
        }
        System.out.println("输入目标数");
        while(sc.hasNext()){
            int target = sc.nextInt();
            System.out.println(new Solution01().findNumberIn2DArray(matrix,target));
        }
    }
}
